import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

import org.junit.Test;

public class MyTest {
    @Test
    public void testtrue(){
        boolean[][] graph={{false,true,true,false,false},{true,false,true,true,true},{true,true,false,false,false},{false,true,false,false,false},{false,true,false,false,false}};
        boolean[] isReached=new boolean[graph.length];
        ArrayList<Integer> path=new ArrayList<Integer>();
        DFS(graph, isReached, 0, 4,path);
        for(int i:path){
            System.out.print("->"+(char)(i+65));
        }
    }
    
    private boolean DFS(boolean[][] graph,boolean[] isReached,int startPoint,int finishPoint,ArrayList<Integer> path){
        if(isReached[finishPoint]){
            return true;
        }else{
            if(!isReached[startPoint]){
                isReached[startPoint]=true;
                path.add(startPoint);
                boolean flage=true;
                for(int i=0;i<isReached.length;i++){
                    if(graph[startPoint][i]&&DFS(graph, isReached, i, finishPoint, path)){                        
                        flage=false;
                        break;
                    }
                }
                if(flage){
                    path.remove(path.size()-1);
                }
                return !flage;
            }else{
                return false;
            }
        }
        //System.out.println("Can't find");
    }


    private boolean BFS(boolean[][] graph,boolean[] isReached,int startPoint,int finishPoint,ArrayList<Integer> path){
        Queue<Integer> queue=new LinkedList<Integer>();
        isReached[startPoint]=true;
        boolean flage=true;
        path.add(startPoint);
        if(startPoint==finishPoint){
            return true;
        }
        for(int i=0;i<isReached.length;i++){
            if(graph[startPoint][i]&&!isReached[i]){
                queue.offer(i);
                flage=false;
            }
        }
        if(flage){
            path.remove(path.size()-1);
        }
        while(!queue.isEmpty()){
            int node=queue.poll();
            isReached[node]=true;
            flage=true;
            path.add(node);
            if(node==finishPoint){
                return true;
            }
            for(int i=0;i<isReached.length;i++){
                if(graph[node][i]&&!isReached[i]){
                    queue.offer(i);
                    flage=false;
                }
            }
            if(flage){
                path.remove(path.size()-1);
            }
        }
        return false;
    }
}
